#include <string.h>
#include "lz77.h"
#include "../myTypes.h"


#define DICTIONARYLEN	255	//2^8 - 1 car il faut coder 0
#define READBUFLEN		255	// choisir n=(2^k)-1

typedef struct{
	bloc_t	beg;	//i
	bloc_t	len;	//j
	byte	c;		//k
} lz77code_t;


uint dicLen = 0;	//initialisé par LZ77_init()
uint rbufLen= 0;	//initialisé par LZ77_init()

uint begCodeSize=0;	//initialisé par LZ77_init()
uint lenCodeSize=0;	//initialisé par LZ77_init()
static int verbose =0;  //verbose mode, initialisé par LZ77_compress()

//-----------------------------------------------------------------------------
void LZ77_init(uint dictionaryLen, uint readBufLen)
//-----------------------------------------------------------------------------
{
	bloc_t i,log=1;

	dicLen	= dictionaryLen;
	rbufLen	= readBufLen;

	for(i=dicLen; i>1; i/=2){log++;}
	begCodeSize = log;

	log=1;
	for(i=rbufLen; i>1; i/=2){log++;}
	lenCodeSize = log;
	if(verbose)
	  printf("Initialisation du codage sur (%d,%d) bits\n",begCodeSize,lenCodeSize);
}


//-----------------------------------------------------------------------------
lz77code_t LZ77_getCode(bitbuf_t * buf)
//-----------------------------------------------------------------------------
//Recherche brutale dans le dictionaire du plus long facteur de substitution
//uniquement si'il reste des données a consommer
{
	lz77code_t code;
	byte * win=buf->curs-dicLen; //pointeur du début du dictionnaire
	uint localdiclen ; //longueur du dictionnaire "local"
	uint localreadbuflen; // longueur de la fenetre de lecture "locale"

	byte * winEnd=buf->curs+rbufLen;	//pointeur vers la fin de fenetre de lecture
	byte * buffEnd = buf->data+buf->len;  //pointeur vers la fin du buffer

	if (win < buf->data){localdiclen=buf->curs-buf->data;} //initialisation de la taille du dico local
	else {localdiclen=dicLen;}


	if (winEnd>buffEnd)
	{localreadbuflen=buffEnd-buf->curs;} //initialisation de la taille de la fenêtre de lecture locale
	else {localreadbuflen=rbufLen;}

	byte * beg=win;			//debut du facteur
	byte * p=beg;			//pointeur de recherche dans le dictionnaire
	//(pour trouver le plus long facteur debutant à beg)
	byte * rbuf= buf->curs;	//pointeur de recherche dans le tampon de lecture



	uint maxfactLen=0;		//taille du plus long facteur trouvé
	uint factLen=0;			//taille du facteur courrant
	byte * fact = beg;




	while( beg < buf->curs ) //pour tout le dictionnaire
	{
		rbuf=buf->curs;
		factLen =0;
		while((p < win+dicLen) && (rbuf < winEnd) && (*rbuf == *p) )
			//tq  non fin dico ET non fin tampon de lecture ET car identiques
		{
			rbuf++; p++; factLen++;
		}
		if( factLen > maxfactLen )
		{
			maxfactLen = factLen;
			fact = beg;
			if( maxfactLen == rbufLen )
			{
				//printf("BREAK !!!!");
				break;
			}
		}

		beg++;
		p=beg;
	}



	if((!localdiclen)|(maxfactLen == 0)) //retour code spécial
	{
		code.beg = 0;
		code.len = 1;
		code.c	  = *rbuf;

	}else{	//retour code normal
		code.beg = (buf->curs - fact);
		code.len = maxfactLen;
		//code.c	 = ... inutile
	}
	if(verbose)
	  if(code.beg)	printf("(%d,%d) ",code.beg, code.len);
	  else		printf("%c ",code.c);


	buf->curs+=code.len; //décalage de la fenêtre de la taille de ce que l'on a ajouté dans le dico

	return code;

}


//-----------------------------------------------------------------------------
bitcount_t LZ77_writeCode(lz77code_t * code, bitbuf_t * dst)
//-----------------------------------------------------------------------------
//Écrire le code dans le buffer => retourne le nombre de bits ecrit
{
	bitcount_t wrote=begCodeSize;

	bit_write(dst, code->beg, begCodeSize);
       
	if(code->beg == 0){
		bit_write(dst, code->c, 8);
		wrote += 8;
	}else{
		//TODO optimiser le nombre de bits pour len en fonction de beg
		bit_write(dst, code->len, lenCodeSize);
		wrote += lenCodeSize;
	}

	return wrote;
}


//-----------------------------------------------------------------------------
bitcount_t LZ77_readCode(lz77code_t * code, bitbuf_t * dst)
//-----------------------------------------------------------------------------
//Lire un code depuis le buffer => retroune le nombre de bits lus
{
	bitcount_t read= begCodeSize;

	code->beg = bit_read(dst, begCodeSize);
	if(code->beg == 0){
		code->len = 0;
		code->c   = bit_read(dst, 8);
		read += 8;
	}else{
		code->len = bit_read(dst, lenCodeSize);
		read += lenCodeSize;
	}

	return read;
}


//-----------------------------------------------------------------------------
void LZ77_encode(bitbuf_t * dst, bitbuf_t * src)
//-----------------------------------------------------------------------------
{
  size_t i = 0;
  lz77code_t	code;
  while(i<src->len)
    {
      //On recupere le code
      code=LZ77_getCode(src);
      //On l'ecrit dans le buffer de destination
      LZ77_writeCode(&code, dst);
      //On passe à la suite
      i+=(!code.len)?8:code.len*8;
    }
  dst->len =  bit_getpos(dst);
}


//-----------------------------------------------------------------------------
void LZ77_decode(bitbuf_t * dst, bitbuf_t * src)
//-----------------------------------------------------------------------------
{
	size_t i,tmp;
	lz77code_t	code;
	i = 0;
	while(i<(src->len))
	{
		tmp = LZ77_readCode(&code, src);
	     
		i+= tmp;

		if(code.beg != 0){
		       
			//substitution
			memcpy(dst->curs, (dst->curs - code.beg), code.len);
			dst->curs += code.len;
		}else{
			//insertion d'un nouveau caractère
			*dst->curs = code.c;
			dst->curs++;
		}
	}
	dst->len = bit_getpos(dst);

}


//-----------------------------------------------------------------------------
int LZ77_writeHeader(FILE * out, lz77header * header)
//-----------------------------------------------------------------------------
{
	fwrite(header->id,4,1,out);
	fwrite(&header->dicLen,2,1,out);
	fwrite(&header->readbuflen,2,1,out);
	fwrite(&header->oriSize,4,1,out);
	fwrite(&header->bufLen, 2, 1, out);

	return 14;
}


//-----------------------------------------------------------------------------
void LZ77_readHeader(FILE * in, lz77header * header)
//-----------------------------------------------------------------------------
{
	header->dicLen=0;
	header->readbuflen=0;
	header->oriSize=0;
	header->bufLen =0;

	fread(header->id,4,1,in);
	fread(&header->dicLen,2,1,in);
	fread(&header->readbuflen,2,1,in);
	fread(&header->oriSize,4,1,in);
	fread(&header->bufLen, 2, 1, in);
}


//-----------------------------------------------------------------------------
void LZ77_compress(FILE * out, FILE * in, int verb)
//-----------------------------------------------------------------------------
//premier rush on fixe les buffers a 8ko et on gaspille des bits dans le fichier
//TODO ne plus faire de gaspillage de bits
{
        verbose = verb;
	bitbuf_t src,dst;
	uint bufLen = 8192;
	int len=0;
	size_t read=0,wrote=0;
	size_t fileLen;

	//calcul de la taille du fichier
	fseek(in,0,SEEK_END);
	fileLen = ftell(in);
	rewind(in);

	if(verbose)
	  printf("filLen= %d\n",fileLen);

	lz77header header={LZ77ID,DICTIONARYLEN,READBUFLEN,fileLen,bufLen};

	wrote = LZ77_writeHeader(out,&header);

	//initialisation des buffers
	bit_initBuf(&src,bufLen*8);
	bit_initBuf(&dst,(bufLen+(bufLen/3))*8);

	//initialisation de l'algo
	LZ77_init(DICTIONARYLEN,READBUFLEN);
	updateBar(0.);

	while(!feof(in))
	{
		len=fread(src.data, 1, bufLen, in);
		src.len=8*len;	//1octet = 8bits
		read+=len;

		updateBar((double)read/fileLen);
		//affichage du taux de compresion
		if(verbose)
		  printf(" (%02d%%)",(int)( 100.*( (double)wrote/(double)read)));

		bit_seek(&src,0,0,BITSEEK_SET);
		bit_seek(&dst,0,0,BITSEEK_SET);

		LZ77_encode(&dst,&src);

		if(verbose)
		  {
		    printf("\n"); bit_print(&dst);printf("\n || ");
		    int i;
		    for(i=0; i<(dst.len)/8 +1; i++)
		      printf("0x%02X ",dst.data[i]);
		    printf(" ||\n");
		  }

		//écrire la source encodée
		fwrite(&dst.len,3, 1, out);
		fwrite(dst.data, (dst.len/8)+1,1,out);
		wrote+= 3 + (dst.len/8)+1;
		if(verbose)
		  printf("src.len = %dbits dst.len= %dbits\n",src.len,dst.len);
	}
	updateBar(1.); printf(" (%02d%%)",(int)( 100.*( (double)wrote/(double)read)));
	printf("\n :D\n");

	bit_freeBuf(&src);
	bit_freeBuf(&dst);
}

//-----------------------------------------------------------------------------
void LZ77_decompress(FILE * out, FILE * in, int verb)
//-----------------------------------------------------------------------------
{
        verbose = verb;
	bitbuf_t src,dst;
	uint bufLen=0;
	size_t wrote=0;
	lz77header header;

	LZ77_readHeader(in, &header);

	bufLen=header.bufLen; // taille du buffer
	if(verbose)
	  printf("bufLen =%dbytes oriSize=%dbytes\n",bufLen, header.oriSize);

	//initialisation des buffers
	bit_initBuf(&src,(bufLen+(bufLen/3))*8);
	bit_initBuf(&dst,bufLen*8);

	//initialisation de l'algo
	LZ77_init(header.dicLen,header.readbuflen);
	updateBar(0.);

	while( !feof(in) )
	{
		src.len=0;
		fread(&(src.len), 3,1,in);
		if(verbose)
		  printf("src.len = %d bits arondis à %d bytes \n",src.len,(src.len/8)+1);

		updateBar((double)wrote/header.oriSize);

		bit_seek(&src,0,0,BITSEEK_SET);
		bit_seek(&dst,0,0,BITSEEK_SET);

		fread(src.data, 1, (src.len/8)+1, in);
		LZ77_decode(&dst, &src);
		if(verbose)
		  printf("\n%d - dst.len = %dbits (%dbytes) \n",__LINE__,dst.len,dst.len/8);
		fwrite(dst.data, dst.len/8 , 1, out);	//dst.len = 8*k
		wrote+=dst.len/8;
	}
	updateBar(1.);

	printf("\n :D\n");
	bit_freeBuf(&src);
	bit_freeBuf(&dst);
}







/*
//-----------------------------------------------------------------------------
int main()
//-----------------------------------------------------------------------------
{
	bitbuf_t dst, src, dst2;
	char msg[]="aabbaaaaaaaaabbaabbbaaaabba";//ababbaabaaaaaabbbbabbbaaaabbaa";
	int len = 26;
	int i;

	printf("%s (%d)\n",msg,len);

	LZ77_init(8,8);

	bit_initBuf(&dst, len*8);
	bit_initBuf(&src,len*8);
	bit_initBuf(&dst2,len*8);

//	src = LZ77_createEncodeBuffer(len);
	for(i=0; i<len; i++) {src.data[i] = msg[i];}




	LZ77_encode(&dst, &src);
	bit_print(&dst);
	printf("lz77_encode => %d\n",bit_getpos(&dst));

	bit_seek(&dst,0,0,BITSEEK_SET);
	printf("seekset => %d\n",bit_getpos(&dst));

//	dst2 = LZ77_createDecodeBuffer(len);

	bzero(dst2.data,len);
	LZ77_decode(&dst2,&dst);
	printf("decode -> \"%s\"\n",dst2.data);


	return EXIT_SUCCESS;
}
*/
//

